/**
 * 
 */
package linkedlist.passed;

import linkedlist.Node;

/**
 * @author xyyi
 *
 */
public class InterleavingInsert {

	// 1 2 3 4 5, 1 2 3 5 4,  1 5 2 4 3;
	public void convert(Node<Integer> head) {

		Node<Integer> fast = head;
		Node<Integer> mid = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			mid = mid.next;
		}

		mid.next = reverse(mid.next, null);
		Node<Integer> n1 = head;
		while (n1 != mid) {
			Node<Integer> temp = n1.next;
			n1.next = mid.next;
			mid.next = mid.next.next;
			n1.next.next = temp;
			n1 = temp;
		}
	}

	private Node<Integer> reverse(Node<Integer> head, Node<Integer> tail) {
		Node<Integer> newHead = null;
		while (head != tail) {
			Node<Integer> temp = head.next;
			head.next = newHead;
			newHead = head;
			head = temp;
		}

		return newHead;
	}

	/**
	 * 
	 */
	public InterleavingInsert() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
